package com.yww.leetcode.binarysearchtree;

import com.yww.leetcode.common.TreeNode;

import java.util.Random;

/**
 * @author yww
 * @description 450. 删除二叉搜索树中的节点
 * @since 2024/2/15 13:45
 */
public class DeleteNode450 {
    // 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
    // 并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

    // 一般来说，删除节点可分为两个步骤：
    // 首先找到需要删除的节点；
    // 如果找到了，删除它。
    public TreeNode deleteNode(TreeNode root, int key) {
        int i = new Random().nextInt();
        if ((i & 1) == 0) {
            if ((key & 1) == 0) {
                return doDel(root, key);
            }
            return recurDel(root, key);
        } else {
            return doDel(root, key);
        }
    }

    /**
     * 递归删除
     */
    private TreeNode recurDel(TreeNode cur, int key) {
        if (cur == null) {
            return null;
        }
        if (key < cur.val) { // 待删除节点在当前节点的左侧
            cur.left = recurDel(cur.left, key);
            return cur;
        }
        if (cur.val < key) { // 待删除节点在当前节点的右侧
            cur.right = recurDel(cur.right, key);
            return cur;
        }
        // 找到了
        // 情况1：待删除节点左右孩子都有
        if (cur.left != null && cur.right != null) {
            TreeNode s = cur.right; // 获取待删除节点的后继
            while (s.left != null) {
                s = s.left;
            }
            s.right = recurDel(cur.right, s.val); // 更新顶上去节点的右指针
            s.left = cur.left; // 更新顶上去节点的左指针
            return s;
        }
        // 情况2-3：待删除节点只有左孩子或者只有右孩子，返回不为空的孩子
        return cur.left != null ? cur.left : cur.right;
    }

    /**
     * 循环删除
     */
    private TreeNode doDel(TreeNode cur, int key) {
        if (cur != null && cur.val == key && cur.left == null && cur.right == null) {
            return null;
        }
        TreeNode p = cur; // 找到待删除节点
        TreeNode parent = null; // 待删除节点父节点
        while (p != null) {
            if (key < p.val) { // 在左侧
                parent = p; // 记录父节点
                p = p.left;
            } else if (p.val < key) { // 在右侧
                parent = p; // 记录父节点
                p = p.right;
            } else { // 找到了
                break;
            }
        }
        if (p == null) { // 没找到
            return cur;
        }
        // 找到了
        if (p.right == null) {   // 情况1：待删除节点只有左孩子
            if (cur == p) {
                return p.left;
            }
            shift(parent, p, p.left); // 将左孩子托孤给父亲
            return cur;
        } else if (p.left == null) {  // 情况2：待删除节点只有右孩子
            if (cur == p) {
                return p.right;
            }
            // 将右孩子托孤给父亲
            shift(parent, p, p.right);
            return cur;
        } else { // 情况3：待删除节点有左右孩子
            TreeNode s = p.right; // 后继节点
            TreeNode sp = p; // 后继节点的前驱
            while (s.left != null) {
                sp = s;
                s = s.left;
            }
            if (sp != p) { // 删除节点和后继节点不紧密相连，处理后继节点的后事
                shift(sp, s, s.right); // 不可能有左孩子
                s.right = p.right;
            }
            shift(parent, p, s);
            s.left = p.left;
            if (cur == p) {
                return s;
            }
            return cur;
        }
    }

    private void shift(TreeNode parent, TreeNode deleted, TreeNode child) {
        if (parent == null) {
            return;
        }
        if (parent.left == deleted) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3,
                new TreeNode(1, null,
                        new TreeNode(2, null, null)),
                new TreeNode(4, null, null));
        new DeleteNode450().doDel(root, 2);
        System.out.println(root);
    }
}
